package com.hr.tuling.list;

/**
 * @author ：zhz
 * @date ：Created in 2020/12/22
 * @version: V1.0
 * @slogan: 天下风云出我辈，一入代码岁月催
 * @description: 环形单链表的实现
 **/
public class CycleSingleLinkedList {
    /**
     * 用于保存单链表中的首节点
     */
    private CycleNode headNode;

    /**
     * 用于保存单链表中的尾节点
     */
    private CycleNode lastNode;

    /**
     * 用于保存单链表中节点的个数
     */
    private int size;

    /**
     * 添加元素
     *
     * @param element 需要添加的数据
     */
    public void add(Object element) {
        // 1.把需要添加的数据封装成节点对象
        CycleNode node = new CycleNode(element);
        // 2.处理单链表为空表的情况
        if (headNode == null) {
            // 2.1 把 node 节点设置为单链表的首节点
            headNode = node;
            // 2.2 把 node 节点设置为单链表的尾节点
            lastNode = node;
        } else {// 3.处理单链表不是空表的情况
            // 3.1 让 lastNode 指向 node 节点
            lastNode.next = node;
            // 3.2 更新 lastNode 的值
            lastNode = node;
        }
        // 4.设置 lastNode 的 next 值为 headNode
        lastNode.next = headNode;
        // 5.更新 size 的值
        size++;
    }

    /**
     * 根据序号获取元素
     *
     * @param index 序号
     * @return 序号所对应节点的数据值
     */
    public Object get(int index) {
        // 1.如果序号的取值小于 0，则证明是不合法的情况
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("序号不合法，index：" + index);
        }
        // 2.根据序号获得对应的节点对象
        CycleNode node = node(index);
        // 3.获取并返回 node 节点的数据值
        return node.data;
    }


    /**
     * 根据序号删除元素
     *
     * @param index 序号
     */
    public void remove(int index) {
        // 1.判断序号是否合法，合法取值范围：[0, size - 1]
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("序号不合法，index：" + index);
        }
        // 2.处理删除节点在开头的情况
        if (index == 0) {
            // 2.1 获得删除节点的后一个节点
            CycleNode nodeNext = headNode.next;
            // 2.2 设置 headNode 的 next 值为 null
            headNode.next = null;
            // 2.3 设置 nextNode 为单链表的首节点
            headNode = nodeNext;
            // 2.4 设置 lastNode 的 next 值为 headNode
            lastNode.next = headNode;
        } else if (index == size - 1) {// 3.处理删除节点在末尾的情况
            // 3.1 获得删除节点的前一个节点
            CycleNode preNode = node(index - 1);
            // 3.2 设置 preNode 的 next 值为 null
            preNode.next = null;
            // 3.3 设置 preNode 为单链表的尾节点
            lastNode = preNode;
            // 3.4 设置 lastNode 的 next 值为 headNode
            lastNode.next = headNode;
        } else {   // 4.处理删除节点在中间的情况
            // 4.1 获得 index-1 所对应的节点对象
            CycleNode preNode = node(index - 1);
            // 4.2 获得 index+1 所对应的节点对象
            CycleNode nodeNext = preNode.next.next;//或者 CycleNode nodeNext= node(index+1);
            // 4.3 获得删除节点并设置 next 值为 null
            preNode.next.next = null;//促进gc
            // 4.4 设置 preNode 的 next 值为 nextNode
            preNode.next = nodeNext;
        }
        // 5.更新 size 的值
        size--;
        // 6.判断 size 的值是否为 0，如果 size 的值为 0，则设置 headNode 和 lastNode 为null
        if (size == 0) {
            headNode = null;
            lastNode = null;
        }
    }

    /**
     * 根据序号插入元素
     *
     * @param index   序号
     * @param element 需要插入的数据
     */
    public void add(int index, Object element) {
        // 1.判断序号是否合法，合法取值范围：[0, size]
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("序号不合法，index：" + index);
        }
        // 2.把需要添加的数据封装成节点对象
        CycleNode curNode = new CycleNode(element);

        if (index==0){// 3.处理插入节点在开头位置的情况
            // 3.1 设置 node 的 next 值为 headNode
           curNode.next=headNode;
            // 3.2 设置 node 节点为单链表的首节点
            headNode= curNode;
            // 3.3 设置 lastNode 的 next 值为 headNode
            lastNode.next=headNode;
        }else if (index==size-1){// 4.处理插入节点在末尾位置的情况
            // 4.1 设置 lastNode 的 next 值为 node
            lastNode.next=curNode;
            // 4.2 设置 node 节点为单链表的尾节点
            lastNode=curNode;
            // 4.3 设置 lastNode 的 next 值为 headNode
            lastNode.next=headNode;
        }else{// 5.处理插入节点在中间位置的情况
            // 5.1 获得 index-1 所对应的节点对象
            CycleNode preNode = node(index - 1);
            // 5.2 获得 index 所对应的节点对象
            CycleNode cNode = preNode.next;
            // 5.3 设置 preNode 的 next 为 node
            preNode.next=curNode;
            // 5.4 设置 node 的 next 为 curNode
                curNode.next=cNode;
        }
        // 6.更新 size 的值
        size++;
}

    /**
     * 根据序号获得对应的节点对象
     *
     * @param index 序号
     * @return 序号对应的节点对象
     */
    private CycleNode node(int index) {
        // 1.判断环形单链表是否为空表
        if (headNode == null) {
            throw new NullPointerException("环形单链表为空表");
        }
        // 2.定义一个零时节点，用于辅助单链表的遍历操作
        CycleNode tempNode = headNode;
        // 3.定义一个循环，用于获取 index 对应的节点对象
        for (int i = 0; i < index % size; i++) {
            // 4.更新 tempNode 的值
            tempNode = tempNode.next;
        }
        // 5.返回 index 对应的节点对象
        return tempNode;
    }
}
